﻿#region Using Statements
using System;
using System.Collections.Generic;

using Microsoft.Xna.Framework;
#endregion

namespace QuadTree
{
    /// <summary>
    /// @author: Rob Husfeldt
    /// @author: Zachary Behrmann
    /// </summary>
    class QuadTree
    {
        #region Constants
        // The maximum number of objects in a quad
        // before a subdivision occurs
        private const int MAX_OBJECTS_BEFORE_SUBDIVIDE = 3;
        #endregion

        #region Variables
        // The game objects held at this level of the tree
        private List<GameObject> _objects;

        // This quad's rectangle area
        private Rectangle _rect;

        // This quad's divisions
        private QuadTree[] _divisions;
        #endregion

        #region Properties
        /// <summary>
        /// The divisions of this quad
        /// </summary>
        public QuadTree[] Divisions { get { return _divisions; } }

        /// <summary>
        /// This quad's rectangle
        /// </summary>
        public Rectangle Rectangle { get { return _rect; } }

        /// <summary>
        /// The game objects inside this quad
        /// </summary>
        public List<GameObject> GameObjects { get { return _objects; } }
        #endregion

        #region Constructor
        /// <summary>
        /// Creates a new Quad Tree
        /// </summary>
        /// <param name="x">This quad's x position</param>
        /// <param name="y">This quad's y position</param>
        /// <param name="width">This quad's width</param>
        /// <param name="height">This quad's height</param>
        public QuadTree(int x, int y, int width, int height)
        {
            // Save the rectangle
            _rect = new Rectangle(x, y, width, height);

            // Create the object list
            _objects = new List<GameObject>();

            // No divisions yet
            _divisions = null;
        }
        #endregion

        #region Methods
        /// <summary>
        /// Adds a game object to the quad.  If the quad has too many
        /// objects in it, and hasn't been divided already, it should
        /// be divided
        /// </summary>        
        /// <param name="gameObj">The object to add</param>
        /// /// @author Zachary Behrmann
        public void AddObject(GameObject gameObj)
        {
            //The following before "if(doAnything)" prevents us from having a stack overflow
            //By making sure no two rectangles are in the same place, or some other condition that breaks the code (beofre implementing constant stack overlows occurred)
            bool doAnything = true;
            List<Rectangle> rectList = new List<Microsoft.Xna.Framework.Rectangle>();
            GetAllRectangles(ref rectList);
            foreach (Rectangle R in rectList)
            {
                if (R.Intersects(gameObj.Rectangle))
                    doAnything = false;
            }
            // ACTIVITY: Complete this method

            if (doAnything)
            {
                
                GameObjects.Add(gameObj);


                if (GameObjects.Count > MAX_OBJECTS_BEFORE_SUBDIVIDE)
                {
                    if (_divisions == null)
                        Divide();
                    //int stop = ;
                    for (int j = GameObjects.Count - 1; j >= 0; j--)
                    {

                        QuadTree temp = GetContainingQuad(GameObjects[j].Rectangle);
                        if (temp != null)
                        {
                            temp.AddObject(GameObjects[j]);
                            GameObjects.RemoveAt(j);
                        }
                    }
                }
            }
        }

        /// <summary>
        /// Divides this quad into 4 smaller quads.  Moves any game objects
        /// that are completely contained within the new smaller quads into
        /// those quads and removes them from this one.
        /// </summary>
        /// @author: Zachary Behrmann
        public void Divide()
        {
            if (_divisions == null)
            {
                _divisions = new QuadTree[4];
                for (int i = 0; i < 4; i++)
                {
                    int x = 0, y = 0;

                    switch (i)
                    {
                        case 0: x = _rect.X; y = _rect.Y; break;
                        case 1: x = _rect.X + _rect.Width / 2; y = _rect.Y; break;
                        case 2: x = _rect.X; y = _rect.Y + _rect.Height / 2; break;
                        case 3: x = _rect.X + _rect.Width / 2; y = _rect.Y + _rect.Height / 2; break;
                    }
                    _divisions[i] = new QuadTree(x, y, _rect.Width / 2, _rect.Height / 2);
                }
            }
        }

        // ACTIVITY: Complete this method


        /// <summary>
        /// Recursively populates a list with all of the rectangles in this
        /// quad and any subdivision quads
        /// </summary>
        /// <param name="rects">The reference list to populate</param>
        /// @author: Rob Husfeldt
        public void GetAllRectangles(ref List<Rectangle> rects)
        {
            for (int i = 0; i < _objects.Count; i++)
            {
                rects.Add(_objects[i].Rectangle);
            }
            if (_divisions != null)
            {
                for (int i = 0; i < _divisions.Length; i++)
                {
                    _divisions[i].GetAllRectangles(ref rects);
                }
            }

        }

        /// <summary>
        /// A possibly recursive method that returns the
        /// smallest quad that contains the specified rectangle
        /// </summary>
        /// <param name="rect">The rectangle to check</param>
        /// <returns>The smallest quad that contains the rectangle</returns>
        /// @author: Rob Husfeldt
        public QuadTree GetContainingQuad(Rectangle rect)
        {
            if (_rect.Contains(rect))
            {
                if (_divisions != null)
                {
                    bool childOwned = false;
                    int ownedBy = -1;
                    for (int i = 0; i < _divisions.Length; i++)
                    {
                        if (_divisions[i].Rectangle.Contains(rect))
                        {
                            childOwned = true; ownedBy = i;
                        }
                    }

                    if (!childOwned)
                    {
                        return this;
                    }
                    else
                    {
                        return _divisions[ownedBy].GetContainingQuad(rect);
                    }
                }
                else
                {
                    return this;
                }
            }
            else
            {
                return null;
            }

        }
        #endregion
    }
}
